package com.ly.algorithm.leetcode.tree;

import java.util.*;

/**
 * @Classname Problem637
 * @Description
 * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
 *
 *  
 *
 * 示例 1.txt：
 *
 * 输入：
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 输出：[3, 14.5, 11]
 * 解释：
 * 第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
 *  
 *
 * @Date 2020/9/12 11:23
 * @Author 冷心影翼
 */
public class Problem637 {

    public static void main(String[] args) {
        Solution637 solution637 = new Solution637();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.right = new TreeNode(15);
        root.right.left = new TreeNode(7);
        List<Double> list = solution637.averageOfLevels2(root);
        System.out.println(list);

    }
}

//  3
// 9 10
class Solution637 {
    public List<Double> averageOfLevels1(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.push(root);
        int curCount = 1;
        int nextCount = 0;

        res.add((double) root.val);
        while (!q.isEmpty()) {
            TreeNode pop = q.pop();
            curCount--;
            double sum = 0;
            if(pop.left!=null) {
                q.add(pop.left);
                sum+=pop.left.val;
                nextCount++;
            }
            if(pop.right!=null) {
                q.add(pop.right);
                sum+=pop.right.val;
                nextCount++;
            }
            if(curCount == 0) {
                curCount = nextCount;
                if(nextCount!=0) {
                    sum/=nextCount;
                    res.add(sum);
                }
                nextCount = 0;
            }
        }
        return res;
    }


    public List<Double> averageOfLevels2(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.push(root);

        while (!q.isEmpty()) {
            int curSize = q.size();
            double sum = 0;
            for(int i=0;i<curSize;i++) {
                TreeNode pop = q.pop();
                sum+=pop.val;
                if(pop.left!=null) {
                    q.add(pop.left);
                }
                if(pop.right!=null) {
                    q.add(pop.right);
                }
            }
            sum/=curSize;
            res.add(sum);
        }
        return res;
    }
}